package main.java.indi.zyj.sword;

import main.java.indi.zyj.hot100.base.TreeNode;

public class IsSubStructure {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 需要特判：
        // A === null，这说明 **从某一支出发到达叶子节点 ** 都无法找到一个节点与 B 的根相同，自然就不存在子结构
        // B === null，题目约定空树不是任意一个树的子结构
        if (A == null || B == null) {
            return false;
        }
        /**
         B为A的子结构有3种情况,满足任意一种即可:
         1.B的子结构起点为A的根节点,此时结果为isContain(A,B)
         2.B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
         3.B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
         */
        return compare(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);

    }


    private boolean compare(TreeNode A, TreeNode B) {

        if(B == null){
            //5.A不一定要为空，因为B是A的子树,已经走完了，比如[1]是[1,3]的子树
            return true;
        }
        if(A == null){
            //6.A为空，B不为空必然不是子树
            return false;
        }
        //7.判断当前节点相不相等，左右子树相不相等
        return A.val == B.val && compare(A.left,B.left) && compare(A.right,B.right);

    }


}
